๐Ÿ“‚ B Tree & B+ Tree

@Seongukbaek Posted May 30, 2022 ยท Updated May 30, 2022 ยท 7 min read

์ด์ง„ ํŠธ๋ฆฌ๋Š” ํ•˜๋‚˜์˜ ๋ถ€๋ชจ๊ฐ€ ๋‘ ๊ฐœ์˜ ์ž์‹๋ฐ–์— ๊ฐ€์ง€์ง€ ๋ชปํ•˜๊ณ , ํŽธํ–ฅ๋œ๋‹ค๋ฉด ํƒ์ƒ‰ ํšจ์œจ์ด ์„ ํ˜• ํƒ์ƒ‰๊ธ‰์œผ๋กœ ๋–จ์–ด์ง„๋‹ค. ํ•˜์ง€๋งŒ ์ด์ง„ ํŠธ๋ฆฌ ๊ตฌ์กฐ์˜ ๊ฐ„๊ฒฐํ•จ๊ณผ ๊ท ํ˜•๋งŒ ๋งž๋‹ค๋ฉด ํƒ์ƒ‰, ์‚ฝ์ž…, ์‚ญ์ œ ๋ชจ๋‘ O(logN)O(logN)์˜ ์„ฑ๋Šฅ์„ ๋ณด์ด๋Š” ์žฅ์ ์ด ์žˆ๋‹ค.

๐Ÿงท B Tree

๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค, ํŒŒ์ผ ์‹œ์Šคํ…œ์—์„œ ๋„๋ฆฌ ์‚ฌ์šฉ๋˜๋Š” ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์ผ์ข…์ด๋‹ค. ์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ํ™•์žฅํ•˜์—ฌ ๋” ๋งŽ์€ ์ˆ˜์˜ ์ž์‹์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๊ฒŒ ์ผ๋ฐ˜ํ™”์‹œํ‚จ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. (์ด์ง„ ํŠธ๋ฆฌ๋Š” ์•„๋‹ˆ๋‹ค!)

  • ์ž์‹ ์ˆ˜์— ๋Œ€ํ•œ ์ผ๋ฐ˜ํ™”๋ฅผ ์ง„ํ–‰ํ•˜๋ฉด์„œ, ํ•˜๋‚˜์˜ ๋ ˆ๋ฒจ์— ๋” ์ €์žฅํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ๋ฟ ์•„๋‹ˆ๋ผ ํŠธ๋ฆฌ์˜ ๊ท ํ˜•์„ ์ž๋™์œผ๋กœ ๋งž์ถฐ์ฃผ๋Š” ๋กœ์ง ๋˜ํ•œ ๊ฐ–์ถ”์—ˆ๋‹ค.

    • ๋”ฐ๋ผ์„œ, ๊ท ํ˜• ํŠธ๋ฆฌ์˜ ์žฅ์ ๊ณผ ํšจ์œจ์ ์ธ ๋ฐ์ดํ„ฐ ๋กœ๋“œ์˜ ์žฅ์ ์„ ๊ฐ–์ถ”์—ˆ๋‹ค.

๋ ˆ๋ฒจ์— ๋” ๋งŽ์€ ์ €์žฅ์ด ๊ฐ€๋Šฅํ•˜๋‹ค๋Š” ๊ฒƒ์˜ ์žฅ์ 

๋Œ€๋Ÿ‰์˜ ๋ฐ์ดํ„ฐ ์ฒ˜๋ฆฌ ์‹œ, ๊ฒ€์ƒ‰ ๊ตฌ์กฐ์˜ ๊ฒฝ์šฐ ํ•˜๋‚˜์˜ ๋…ธ๋“œ์— ๋งŽ์€ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์€ ํฐ ์žฅ์ ์ด๋‹ค. ๋Œ€๋Ÿ‰์˜ ๋ฐ์ดํ„ฐ๋Š” ๋ฉ”๋ชจ๋ฆฌ๋ณด๋‹ค ๋ธ”๋Ÿญ ๋‹จ์œ„๋กœ ์ž…์ถœ๋ ฅํ•˜๋Š” HDD or SSD์— ์ €์žฅํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

  • ex. ํ•œ ๋ธ”๋Ÿญ์ด 1024๋ฐ”์ดํŠธ๋ฉด, 2๋ฐ”์ดํŠธ๋ฅผ ์ฝ์œผ๋‚˜ 1024๋ฐ”์ดํŠธ๋ฅผ ์ฝ์œผ๋‚˜ ๋˜‘๊ฐ™์€ ์ž…์ถœ๋ ฅ ๋น„์šฉ์ด ๋ฐœ์ƒํ•œ๋‹ค. ๋”ฐ๋ผ์„œ ํ•˜๋‚˜์˜ ๋…ธ๋“œ๋ฅผ ๋ชจ๋‘ 1024๋ฐ”์ดํŠธ๋กœ ๊ฝ‰ ์ฑ„์›Œ์„œ ์กฐ์ ˆํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด ํšจ์œจ์ ์ผ ๊ฒƒ์ด๋‹ค.

B Tree๋Š” ์ด๋Ÿฌํ•œ ์žฅ์ ์„ ํ† ๋Œ€๋กœ ๋งŽ์€ DB ์‹œ์Šคํ…œ์˜ ์ธ๋ฑ์Šค ์ €์žฅ ๋ฐฉ๋ฒ•์œผ๋กœ ์• ์šฉํ•˜๊ณ  ์žˆ๋‹ค.

๐Ÿชš ๊ทœ์น™

  • ๋…ธ๋“œ์˜ ์ž๋ฃŒ์ˆ˜๊ฐ€ N๊ฐœ์ด๋ฉด, ์ž์‹ ์ˆ˜๋Š” N + 1์ด์–ด์•ผ ํ•œ๋‹ค.
  • ๊ฐ ๋…ธ๋“œ์˜ ์ž๋ฃŒ๋Š” ์ •๋ ฌ๋œ ์ƒํƒœ์—ฌ์•ผ ํ•œ๋‹ค.
  • ๋ฃจํŠธ ๋…ธ๋“œ๋Š” ์ ์–ด๋„ 2๊ฐœ ์ด์ƒ์˜ ์ž์‹์„ ๊ฐ€์ ธ์•ผ ํ•œ๋‹ค.
  • ๋ฃจํŠธ ๋…ธ๋“œ๋ฅผ ์ œ์™ธํ•œ ๋ชจ๋“  ๋…ธ๋“œ๋Š” ์ ์–ด๋„ M/2๊ฐœ์˜ ์ž๋ฃŒ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์–ด์•ผ ํ•œ๋‹ค.
  • ์™ธ๋ถ€ ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋Š” ๋ชจ๋‘ ๊ฐ™๋‹ค.
  • ์ž…๋ ฅ ์ž๋ฃŒ๋Š” ์ค‘๋ณต์ด ์—†์–ด์•ผ ํ•œ๋‹ค.

๐Ÿงท B+ Tree

B Tree

๋ฐ์ดํ„ฐ์˜ ๋น ๋ฅธ ์ ‘๊ทผ์„ ์œ„ํ•œ ์ธ๋ฑ์Šค ์—ญํ• ๋งŒ ํ•˜๋Š” ๋น„๋‹จ๋ง ๋…ธ๋“œ๊ฐ€ ์ถ”๊ฐ€๋กœ ์žˆ๋Š” ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ๊ธฐ์กด์˜ B Tree์™€ ๋ฐ์ดํ„ฐ์˜ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„๋œ ์ƒ‰์ธ ๊ตฌ์กฐ์ด๋‹ค.

  • B Tree์˜ ๋ณ€ํ˜• ๊ตฌ์กฐ๋กœ, index ๋ถ€๋ถ„๊ณผ leaf ๋…ธ๋“œ๋กœ ๊ตฌ์„ฑ๋œ ์ˆœ์ฐจ ๋ฐ์ดํ„ฐ ๋ถ€๋ถ„์œผ๋กœ ์ด๋ฃจ์–ด์ง„๋‹ค. ์ธ๋ฑ์Šค ๋ถ€๋ถ„์˜ key ๊ฐ’์€ leaf์— ์žˆ๋Š” key ๊ฐ’์„ ์ง์ ‘ ์ฐพ์•„๊ฐ€๋Š”๋ฐ ์‚ฌ์šฉํ•œ๋‹ค.
  • p (fanout) ์ด๋ผ๋Š” ๊ฐ’์œผ๋กœ ํ•œ node์— ๋ช‡ ๊ฐœ์˜ entry๊ฐ€ ์ฑ„์›Œ์ ธ์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค.

๐Ÿชš ์žฅ์ 

  • ๋ธ”๋ก ์‚ฌ์ด์ฆˆ๋ฅผ ๋” ๋งŽ์ด ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. (key ๊ฐ’์— ๋Œ€ํ•œ HDD ์ ‘๊ทผ ์ฃผ์†Œ๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.)
  • leaf ๋…ธ๋“œ๋ผ๋ฆฌ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ๋ฒ”์œ„ ํƒ์ƒ‰์— ๋งค์šฐ ์œ ๋ฆฌํ•˜๋‹ค.

๐Ÿชš ๋‹จ์ 

  • B Tree์˜ ๊ฒฝ์šฐ ์ตœ์ƒ ์ผ€์ด์Šค์—์„œ๋Š” ๋ฃจํŠธ์—์„œ ๋๋‚  ์ˆ˜ ์žˆ์ง€๋งŒ, B+ Tree๋Š” ๋ฌด์กฐ๊ฑด leaf ๋…ธ๋“œ๊นŒ์ง€ ๋‚ด๋ ค๊ฐ€๋ด์•ผ ํ•œ๋‹ค.

    • ํƒ์ƒ‰ ๋น„์šฉ์ด ํŠธ๋ฆฌ์˜ ๋†’์ด์— ๋น„๋ก€ํ•˜๊ฒŒ ๋œ๋‹ค!

๐Ÿชš ์‚ฝ์ž…

  • ์‚ฝ์ž…ํ•˜๋ ค๋Š” entry๊ฐ€ ์œ„์น˜ํ•  ๊ณณ์„ ์ฐพ๋Š”๋‹ค.
  • ํ•ด๋‹น node๊ฐ€ ์ถฉ๋ถ„ํ•œ ๊ณต๊ฐ„์ด ์žˆ๋‹ค๋ฉด ์‚ฝ์ž…ํ•˜๊ณ  ์ข…๋ฃŒํ•œ๋‹ค.
  • ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ, ํ•ด๋‹น node๋ฅผ ๋ถ„๋ฆฌํ•œ๋‹ค.

    • node์˜ ์—”ํŠธ๋ฆฌ๋“ค์„ ๋ถ„๋ฐฐํ•˜๊ณ , middle key ๋ฅผ COPY UPํ•œ๋‹ค.

PUSH UPํ•˜๋ฉด, middle key ์— ๋Œ€ํ•œ Data pointer๊ฐ€ ์†์‹ค๋˜๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

๐Ÿชš ์‚ฝ์ž… ์ดํ›„ ...

AfterInsertionB Tree

B+ Tree์— node๋ฅผ ์‚ฝ์ž…ํ•œ ์ดํ›„ ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ ์ฆ๊ฐ€ํ•˜์ง€ ์•Š์„ ์ˆ˜๋„ ์žˆ๊ณ , ์ฆ๊ฐ€ํ•  ์ˆ˜๋„ ์žˆ๋‹ค.

  • B+ Tree์˜ ํƒ์ƒ‰ ๋น„์šฉ์€ ํŠธ๋ฆฌ์˜ ๋†’์ด์— ๋น„๋ก€ํ•œ๋‹ค.
  • ํŠธ๋ฆฌ๋ฅผ ์žฌ๋ถ„๋ฐฐํ•จ์œผ๋กœ์จ, ๋†’์ด๋ฅผ ๋‚ฎ์ถœ ์ˆ˜ ์žˆ๋‹ค!

์žฌ๋ถ„๋ฐฐ๋ฅผ ํ†ตํ•ด ํƒ์ƒ‰ ๋น„์šฉ์„ ๋‚ฎ์ถœ ์ˆ˜๋Š” ์žˆ์ง€๋งŒ, ํ‰๊ท  I/O ๋ฐ”์šฉ์„ ์ฆ๊ฐ€์‹œํ‚จ๋‹ค.

๐Ÿชš ์‚ญ์ œ

  • ๋ฃจํŠธ๋ถ€ํ„ฐ, ํ•ด๋‹น entry๊ฐ€ ์กด์žฌํ•˜๋Š” leaf node๋ฅผ ์ฐพ๋Š”๋‹ค.
  • ํ•ด๋‹น node์—์„œ entry๋ฅผ ์ง€์›Œ๋„ ์ฑ„์›Œ์ ธ์•ผ ํ•˜๋Š” p ๋ฅผ ๋งŒ์กฑํ•œ๋‹ค๋ฉด ๊ทธ๋Œ€๋กœ ์‚ญ์ œํ•œ๋‹ค.
  • ์ง€์šด ํ›„ node์˜ entry ์ˆ˜๊ฐ€ p - 1 ์ด๋ผ๋ฉด, ์ฃผ๋ณ€ leaf node(๊ฐ™์€ ๋ถ€๋ชจ๋ฅผ ๊ฐ€์ง€๋Š” ์ฃผ๋ณ€ node)๋กœ๋ถ€ํ„ฐ entry๋ฅผ ๋นŒ๋ ค์™€ p ๋ฅผ ๋งŒ์กฑ์‹œํ‚จ๋‹ค.

    • ์ด๋Š” middle key ์˜ ๋ณ€๊ฒฝ์„ ์œ ๋ฐœํ•œ๋‹ค.
    • ๋งŒ์•ฝ ์ฃผ๋ณ€ leaf node๋กœ๋ถ€ํ„ฐ ๋นŒ๋ ค์˜ฌ ์ˆ˜ ์—†๋‹ค๋ฉด, ๊ทธ leaf node์™€ ๊ฒฐํ•ฉํ•œ๋‹ค.
    • ๊ฒฐํ•ฉ์ด ๋ฐœ์ƒํ•˜๋ฉด, ๋‘˜ ์ค‘ ํ•œ node๋Š” ์ œ๊ฑฐํ•œ๋‹ค.
    • ๊ฒฐํ•ฉ์„ ํ†ตํ•ด ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ ๊ฐ์†Œํ•  ์ˆ˜๋„ ์žˆ๋‹ค.

๐Ÿงท B Tree์™€ B+ Tree ๋น„๊ต

  • B Tree๋Š” ๊ฐ ๋…ธ๋“œ์— ๋ฐ์ดํ„ฐ๊ฐ€ ์ €์žฅ๋œ๋‹ค.
  • B+ Tree๋Š” index ๋…ธ๋“œ์™€ leaf ๋…ธ๋“œ๋กœ ๋ถ„๋ฆฌ๋˜์–ด ์ €์žฅ๋œ๋‹ค. (๋˜ํ•œ leaf ๋…ธ๋“œ๋Š” ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์–ด ์ž„์˜ ์ ‘๊ทผ์ด๋‚˜ ์ˆœ์ฐจ ์ ‘๊ทผ ๋ชจ๋‘ ์„ฑ๋Šฅ์ด ์ข‹๋‹ค.)
  • B Tree๋Š” ๊ฐ ๋…ธ๋“œ์—์„œ key์™€ data ๋ชจ๋‘ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๊ณ , data๋Š” disk block์œผ๋กœ ํฌ์ธํ„ฐ๊ฐ€ ๋  ์ˆ˜ ์žˆ๋‹ค.
  • B+ Tree๋Š” ๊ฐ ๋…ธ๋“œ์—์„œ key๋งŒ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ๋‹ค. ๋”ฐ๋ผ์„œ data๋Š” ๋ชจ๋‘ leaf ๋…ธ๋“œ์—๋งŒ ์กด์žฌํ•œ๋‹ค.

    • B+ Tree์˜ ์‚ฝ์ž…๊ณผ ์‚ญ์ œ๋Š” ๋ชจ๋‘ leaf ๋…ธ๋“œ์—์„œ๋งŒ ๋ฐœ์ƒํ•œ๋‹ค.

๐Ÿ“• ์ฐธ๊ณ 

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€